package com.sunny.l25;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.concurrent.LinkedBlockingQueue;

public class Solution {

//    public static void main(String[] args) {
//
//        String start = "hit";
//        String end = "cog";
//        HashSet<String> dict = new HashSet<>(Arrays.asList("hot","dot","dog","lot","log"));
//        Solution solution = new Solution();
//        System.out.println(solution.ladderLength(start, end, dict));
//
//    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(!wordList.contains(endWord))
            return 0;
        wordList.remove(endWord);
        return bfs(beginWord, endWord, new HashSet<>(wordList));
    }

//    public int ladderLength(String start, String end, HashSet<String> dict) {
//        return bfs(start, end, dict);
//    }

    public int bfs(String start, String end, HashSet<String> dict){
        int res = Integer.MAX_VALUE;
        dict.add(end);
//        HashSet<String> used = new HashSet<>();
        LinkedBlockingQueue<Node> queue = new LinkedBlockingQueue<>();
        queue.offer(new Node(start, 1));
        while (!queue.isEmpty()){
            Node tmp = queue.poll();
            if(tmp.str.equals(end)){
                if(res>tmp.layer)
                    res = tmp.layer;
            }
//            used.add(tmp.str);
            dict.remove(tmp.str);
            for(String str: dict){
                if(/*used.contains(str) || */-1 == getDigit(tmp.str, str)){
                    continue;
                }
                queue.offer(new Node(str, tmp.layer+1));
            }
        }
        if(res == Integer.MAX_VALUE)
            return 0;

        return res;

    }

    public int getDigit(String str, String next){
        int cnt = 0;
        int digit = -1;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i) != next.charAt(i)){
                cnt++;
                if(digit == -1)
                    digit = i;
            }
        }
        if(cnt > 1){
            return -1;
        }
        return digit;
    }
}

class Node{
    String str;
    int layer;

    public Node(String str, int layer) {
        this.str = str;
        this.layer = layer;
    }
}
